'''
https://leetcode.cn/problems/kth-largest-element-in-an-array/description/
'''
import random
from typing import List


class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        k -= 1
        def process(l, r):
            if l >= r:
                return nums[l]
            x = nums[random.randint(l, r)]
            # x = nums[r]
            board = partition(l, r, x)
            if board[0] <= k <= board[1]:
                return nums[k]
            return process(l, board[0] - 1) if k < board[0] else process(board[1] + 1, r)

        def partition(l, r, x):
            # 左边都是 > x, 右边都是 < x。
            # return board[0] = x的最左位置 board[1] = x的最右位置
            i = l
            left_board, right_board = l-1, r+1
            while i < right_board:
                if nums[i] > x:
                    left_board += 1
                    nums[i], nums[left_board] = nums[left_board], nums[i]
                    i += 1
                elif nums[i] < x:
                    right_board -= 1
                    nums[i], nums[right_board] = nums[right_board], nums[i]
                    # 从右边过来的数，还要继续看
                else:
                    i += 1
            return (left_board + 1, right_board - 1)

        return process(0, len(nums) - 1)

arr = [3,2,3,1,2,4,5,5,6]
res = Solution().findKthLargest(arr, 4)
print(res)